/* 二叉树后序遍历 */
const tree = {
  val: "a",
  left: {
    val: "b",
    left: {
      val: "e",
      left: null,
      right: null,
    },
    right: {
      val: "f",
      left: null,
      right: null,
    },
  },
  right: {
    val: "c",
    left: {
      val: "g",
      left: null,
      right: null,
    },
    right: {
      val: "h",
      left: null,
      right: null,
    },
  },
};

/* 递归版 */
// const postOrder = (root) => {
//   if (!root) return;
//   postOrder(root.left);
//   postOrder(root.right);
//   console.log(root.val);
// };

/* 非递归版 */
const postOrder = (root) => {
  // 左右根, 倒过来就是根右左,
  // 和先序遍历只是差先插入左子树还是右子树的问题

  const stack = [root];
  const outputStack = [];
  while (stack.length) {
    const n = stack.pop();
    outputStack.push(n);
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);
  }

  while (outputStack.length) {
    console.log(outputStack.pop().val);
  }
};

postOrder(tree);
